There is an acknowledged need to improve Internet performance, by distributing or replicating some of the functions of an application server (such as a Web server) across multiple locations. Ideally, a client should receive services from the closest server (in network terms). Other parameters such as the current load and the maximum capacity of each server, as well as the current network load conditions, may also be important.
A common way of directing the client to the server it should use is based upon a directory service or name service, of which the most common and important today is the Domain Name System (DNS). To facilitate understanding of the subsequent description, the next subsection contains a brief introduction into DNS fundamentals. Detailed DNS specifications may be found in the Internet Engineering Task Force (IETF) rfc1034/1035 documents. See www.Internet-Standard.com. Following the description of the DNS fundamentals, we describe the more specific context in which our present invention is intended to solve problems for which the prior art does not provide satisfactory solution.
Domain Name System Fundamentals
Consider an example: a client wishes to access a Web Server named “site.com”. It starts then with issuing a query to a DNS server asking to have the name “site.com” translated into a network address. Today, a network address is typically an Internet Protocol (IP) address which is a unique 32-bit number. This translation process is usually called name resolution. We call the DNS server or servers (or other such name servers) contacted by the client the client's local DNS (LDNS) server. A LDNS server, which is often on the client's corporate premises or at his ISP, may need to query yet other name servers in order to find the requested IP address. Ultimately, this resolution query process stops at an authoritative DNS (ADNS) server for “site.com”, which is a name server that is configured so that it always contains at least one valid IP address corresponding to “site.com”. The ADNS server then responds to the LDNS server, and the LDNS server finally responds to the client, giving an answer to the query it initially received from that client.
Some further remarks about the Domain Name System terminology and principles will be of use to the reader. First, we should mention that the term “ADNS” relates to a given site name (or several site names) for which this DNS server is authoritative. Similarly, the term “LDNS” relates to a “population of clients” which are using a particular DNS server as their local name server. On the other side, DNS servers used as ADNS servers and those playing an LDNS server role differ in their mode of operation. Therefore it makes sense to use both terms in an absolute and not only relative way. Sometimes however a DNS server may play an LDNS server role for some clients and at the same time be an ADNS server for some site names. When we consider such a name server an LDNS server, we simply refer to one specific role of that name server. There exist also “name server roles” other than ADNS server and LDNS server, but they are of no relevance to the present invention.
An important fact about the Domain Name System is that a DNS server receiving a query may only identify the “immediate source” of the query. In this way, an LDNS server queried by a client knows the IP address of the client; but any other DNS server, including the ADNS server, when queried by an LDNS server knows only the IP address of that LDNS server, and not the address of the client who has provoked this query from the LDNS server to the ADNS as a result of its “initial query” to the LDNS server.
For this reason we will never use in the subsequent text the term “client” to signify the source of a query, when the query responder is not an LDNS server. Thus, the source of a query to an LDNS server is some client, and the source of a query to an ADNS server is some LDNS server. The term “client” will be exclusively used to designate an entity which first interacts with its LDNS server to get an address of a site, and then interacts with the application server whose address has been returned by the LDNS server, and which is deemed to provide the services of that site. Typically, such an entity is a computer equipped with a “resolver” program for interacting with its LDNS server, which is called upon by a “browser” program intended to interact with Web-sites.
Another fact that is important for our subsequent considerations is that a DNS server, and more specifically an LDNS server, while receiving from another DNS server an answer bearing some name-to-address resolution record, may decide to store that record in its local memory called “cache”, for a time interval (validity time, also called “time to live”, or TTL) which is also supplied with the record in the answer. During that time interval, the DNS server, while answering all subsequent queries about the same name, will use the cached information instead of repeating its own “upstream” queries. After the TTL of that record expires, the DNS server will “refresh” the information, by re-issuing an upstream query. Eventually it may receive an answer different from the answer that was previously received and cached.
Load Distribution Using Source-Sensitive ADNS Server
The authoritative DNS server for “site.com” may, in fact, have several different addresses corresponding to more than one location, server, or proxy, that are all capable in principle of providing site.com's service. The ADNS server may then choose, among these possibilities, a subset of one or more such locations that are deemed to be the most suitable in the scope of one specific query. The choice can be made based on network proximity (e.g. how close the client is believed to be to each server), communication cost, quality-of-service considerations, load on each server, and other such factors. Some of these factors (such as the total load on each given server) may be learned by the ADNS server directly from the servers because they are client-independent. For example, U.S. Pat. No. 6,205,477 describes a DNS-based method for load distribution according to predefined load metrics for all servers. But many other parameters (such as network distance and load along the path from the client to the server) vary from client to client and thus would appear to require that the ADNS server be able to identify the client who issued the query. The present invention mainly addresses load distribution techniques based on client-dependent parameters. The “network distance” between a client and a server is the most important among those parameters.
Identifying the client who originated a query received by an ADNS server is, however, a difficult task within the scope of the DNS standard to which the presently deployed Internet name service adheres. The problem lies in the above mentioned “two-level” DNS address resolution mechanism: the client queries its LDNS server, rather than an ADNS server, and the LDNS server then issues another query to an ADNS server (with possibly some preparative queries to locate that ADNS itself). When the ADNS server receives a query, it learns only the address of the issuing LDNS server and not the address of the client that issued the “initial” query. This is significant, because one may wish to design the ADNS server to choose a server that is close to the client or stands in some other particular relation to the client. However, since the ADNS server does not learn the name or address of the client, it can only choose a server that is close to the client's LDNS server instead. Since any client is usually configured to use an LDNS server fairly close to the client itself, it may be a reasonable heuristic to base the decision on the LDNS server rather than the client. However, the adequacy of this heuristic varies from situation to situation, and this may be considered as an intrinsic deficiency of such a “per LDNS server redirection method”.
The above mentioned specific behavior of an ADNS server, making the content of its answer to a query depend on the query's source, is not implemented in the most popular DNS server realizations, which are programmed to answer queries in a “source-independent” manner. Nevertheless, such a source-sensitive ADNS server may easily be designed and integrated into existing Internet network, without disturbing the normal operation of other network components, which would not even notice this specific behavior of the ADNS server. In the subsequent considerations, the term “ADNS” includes such a source-sensitive authoritative name server. Load distribution systems based on source-sensitive ADNS server behavior exist in prior art, and are often termed “DNS-based redirection systems”.
Different Approaches to Network Discovery
In order for a DNS-based redirection system to become operational, one must implement yet another system, either stand-alone or integrated with the redirection mechanism, for performing a task that is usually called network discovery. This task consists in collecting and analyzing information about the network proximity between clients, servers, LDNS servers and ADNS servers. Such information and analysis are needed by the ADNS server in order to choose the correct server(s) in each case.
Different approaches to network discovery may a priori be classified in the following way. We have four main types of network components potentially participating in the discovery process: on one side, clients and application servers (such as Web servers or proxies), on the other side LDNS servers and ADNS servers. Clients send requests to servers, and also send queries to LDNS servers; LDNS servers send further queries to ADNS servers. Client programs (browsers, resolvers etc.) may easily be modified or appended in a way to collect and analyze network distance information, e.g., in the form of round trip time, (RTT) on connections they establish with servers. Clients then may use that information themselves to select the best server or pass it to another network component. We call this group of network discovery methods client-cooperative, because it involves active cooperation of clients, which must run modified or supplemented versions of their programs.
One example of such client-cooperative methods is described in U.S. Pat. No. 6,182,139. A client-side located mechanism for best server selection, which operates on the whole list of server addresses as received from the ADNS server. The ADNS server itself may remain “client-independent”.
This whole group of discovery and redirection methods, however, addresses one specific business model for Internet access acceleration, which involves distribution of specific software to the client community and its wide acceptance by the latter. Clients should be ready to install that software, and eventually pay for it. In contrast, we are mostly interested in providing network discovery and redirection methods “invisible” to clients, by modifying application servers and ADNS servers, or by installing specific modules intended to alter external behavior of those otherwise standard servers. Clients and their LDNS servers should not be modified at all. Such a server-based, client-transparent approach adheres to another business model, largely preferred by the community of Web-service providers.
Another approach to network discovery takes advantage of the fact that the server is also able to measure the RTT along a network connection and thus can collect and sort out network proximity data. Even in the absence of any connection, e.g. when communication is using connectionless UDP protocol, the server typically is still able to measure RTT by sending a special ping packet to the client, or, better, a series of such pings. The latter method may be called active, as opposed to the passive TCP-based method, because it performs measurements at any time when decided by the server, and does it by sending extra packets otherwise absolutely unnecessary for normal interaction between the server and its clients. The active method may also be used between network nodes which otherwise are not communicating at all, e.g. a Web server node may ping an LDNS server.
An example of an enhanced ping algorithm is found in U.S. Pat. No. 5,835,720. Generally speaking, ping is only an example of the active method, and TCP RTT measurement only an example of the passive one. The conceptual difference between these two methods is that the active method creates extra communications unnecessary for the applications it intends to serve, while the passive method does not create extra communications. We should also note that a sole ping message to a given IP address does not provide sufficiently reliable information on network distance to that address, because of possibly significant network delay variations. Thus, a whole series of consecutive pings is typically necessary. This may be considered a serious drawback of the active method, as it creates undesirable traffic and may even cause supplementary delay for application traffic itself, which it intends to accelerate.
Another and perhaps even more important drawback of the active method lies in its assumption that the addressee of a ping (or of any other unsolicited packet or message) would reply. This is not always true. An Internet-connected device could drop ping packets received in what it considers to be a heavy load condition. While this may be a temporary problem, for which a solution is to simply repeat pinging at off-peak hours, there is a much more serious problem. An ever increasing number of Internet-connected devices “hide” themselves, for security reasons behind the so-called “firewalls”, or otherwise protect themselves, by filtering out non-solicited incoming packets, including ping packets. This is specifically true for client-side devices, such as individual client computers, corporate local networks or intranets, and also privately run LDNS servers. Even if a client-side device is initially “ping-responsive”, it may later become “ping-rejecting”, specifically because it may have considered itself as being“attacked” by repetitive pings from the same address. Hence the active method may give only partial results for network discovery.
Continuing with our review of current and possible network discovery methods, we observe that measuring (application-)server-to-client distance brings no help to DNS-based redirection, unless we have also learned which LDNS server a client is assigned to. The ADNS server knows nothing about clients, and the application server knows nothing about LDNS servers. One possible solution consists in measuring distances between application servers and LDNS servers, considering that those distances approximate the real distances between the application servers and their clients. Note that this may only be done using an active method since application servers and LDNS servers do not normally communicate at all. Such an approach suffers both from the general drawback of any active method (network pollution) and from a specific drawback of metering possibly irrelevant information—the distance between nodes that are not intended to communicate.
Problems and Needs Addressed by the Present Invention
There is, therefore, a need for a network discovery mechanism for collecting information about relationships between clients and their assigned LDNS servers, such a mechanism being transparent for both clients and LDNS servers, i.e. requiring no modifications to their installed software.
There is a further need for such a mechanism to be passive, that is, creating no extra communications for its operation, especially along network paths leading to clients or to their LDNS servers.
There is also a need for a network distance measuring mechanism, such a mechanism applying a passive approach, and, when used in conjunction with the above passive network discovery mechanism, collecting network distance metrics between a given server and clients assigned to a given LDNS server, in order to obtain an aggregate distance characteristic for the whole population of the users of that LDNS server, instead of metering the possibly irrelevant distance to the LDNS server itself. A passive measurement mechanism of the same type is also needed for metering other client-to-server communication parameters, such as network load or packet loss rate, and assigning aggregate values of those parameters to LDNS servers.
Finally, there is a need for a complete system providing for optimal distribution of client requests (load balancing) among geographically distributed servers, with their subsequent redistribution as a function of changing network load conditions, making use of client-transparent passive network discovery and measurement mechanisms. Existing load balancing systems are based on active and/or client-cooperative approach to network discovery, measurement and monitoring, and therefore do not satisfy the above formulated requirements.
The present invention addresses all these needs.